package 香槟塔;

import org.junit.Assert;

/**
 * 香槟塔
 * <p>
 * 把玻璃杯摆成金字塔的形状，其中第一层有1个玻璃杯，第二层有2个，依次类推到第100层。
 * 从顶层的第一个玻璃杯开始倾倒一些香槟，当顶层的杯子满了，任何溢出的香槟都会立刻等流量的流向左右两侧的玻璃杯。
 * 当左右两边的杯子也满了，就会等流量的流向它们左右两边的杯子，依次类推。
 * 例如，在倾倒一杯香槟后，最顶层的玻璃杯满了。倾倒了两杯香槟后，第二层的两个玻璃杯各自盛放一半的香槟。
 * 在倒三杯香槟后，第二层的香槟满了，此时总共有三个满的玻璃杯。在倒第四杯后，第三层中间的玻璃杯放了一半的香槟，他两边的玻璃杯各大自戊了四分之一的香槟。
 * 现在当倾倒了非负整数杯香槟后，返回第i行j个玻璃杯所盛的香槟占玻璃杯容积的比例（i和j都从0开始）。
 */
public class Solution {
    public static void main(String[] args) {

        /*

          1
         1 2
        1 2 3    1 = 0.5   2 = 1  3 = 0.5

         */
        double v = canWin4(5, 2, 0);
        System.out.println("2,0 = " + v);
        v = canWin4(5, 2, 1);
        System.out.println("2,1 = " + v);
        v = canWin4(5, 2, 2);
        System.out.println("2,2 = " + v);
    }

    /**
     * 动态规则
     */
    private static double canWin4(int n, int row, int col) {

        double[][] ca = new double[100][100];
        ca[0][0] = n * 1.0;

        for (int r = 0; r < row; r++) {
            for (int c = 0; c <= r; c++) {
                double d = (ca[r][c] - 1) / 2;
                if (d > 0) {
                    // 溢出了，累加到下层的杯子中
                    ca[r + 1][c] += d;
                    ca[r + 1][c + 1] += d;
                }
            }
        }
        return Math.min(1, ca[row][col]);
    }

}
